Dwuszereg

Limit pamięci: 32 MB

W dwuszeregu stoi żołnierzy. Trzeba przestawić żołnierzy tak, aby w tym samym szeregu nie było dwóch żołnierzy tego samego wzrostu - wówczas powiemy, że żołnierze są ustawieni poprawnie.

Pojedyncza operacja polega na zamianie miejscami dwóch żołnierzy, którzy są na tej samej pozycji w obu szeregach. Twoim zadaniem jest policzenie minimalnej liczby zamian, jakie trzeba wykonać, aby żołnierze byli ustawieni poprawnie.

Przykład:

Na rysunku mamy dwuszereg złożony z żołnierzy. Strzałkami zaznaczono 3 operacje zamiany, po wykonaniu których żołnierze są ustawieni poprawnie.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę i wzrost żołnierzy, tak jak są ustawieni na początku,
• wyznaczy minimalną liczbę zamian miejscami (żołnierzy stojących na tej samej pozycji w obu szeregach) potrzebnych do poprawnego ustawienia żołnierzy,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita , . W każdym z dwóch szeregów stoi żołnierzy. W każdym z dwóch kolejnych wierszy znajduje się po dodatnich liczb całkowitych pooddzielanych pojedynczymi odstępami. W drugim wierszu znajdują się liczby , ; to wzrost -go żołnierza w pierwszym szeregu. W trzecim wierszu znajdują się liczby , ; to wzrost -go żołnierza w drugim szeregu.

Możesz założyć, że dla danych testowych zawsze możliwe jest poprawne ustawienie żołnierzy.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna nieujemna liczba całkowita - minimalna liczba zamian jakie należy wykonać, aby żołnierze byli poprawnie ustawieni.

Przykład

Dla danych wejściowych:

9
2 5 5 2 7 4 7 3 9
1 6 8 4 6 3 9 1 8

poprawną odpowiedzią jest:

3

Autor zadania: Wojciech Rytter.